A saved secret (e.g., a private key used in cryptography) is under a threat of loss and corruption and a threat of theft. Copying a secret is effective against the former threat. However, copying raises the latter threat of theft. One information security technique for solving this problem is a secret sharing scheme.
The secret sharing scheme divides a secret into a plurality of shares. The secret sharing scheme has a feature: If predetermined shares are collected, the secret can be uniquely reconstructed, but if other shares are collected, no information on the secret is leaked. In this specification, letting n be the number of shares, the respective shares are identified by 1 to n. In the secret sharing scheme, a set of shares capable of reconstructing a secret can be defined by a family Γ of share sets called an access structure. The access structure Γ is a family of sets having, as an element, a set of the identifiers of minimum shares capable of reconstructing a secret. In a secret sharing scheme having the access structure Γ, that a set w of shares can reconstruct a secret means that V which satisfies VεΓ and V⊂W exists for a share identifier set W corresponding to w. The share identifier set W which meets these properties is defined as an access set of Γ.
For example, a secret sharing scheme called a (k,n) threshold scheme has features: (1) Information on a secret cannot be obtained from less than k shares out of n shares. (2) The secret is uniquely reconstructed from k or more shares. The access structure Γ in the (k,n) threshold scheme is defined by a family of sets in which Γ=[V|V⊂[1, . . . , n] and the number of elements of V is k]. Problems when reconstructing a secret in the secret sharing scheme will be examined.
When reconstructing a secret, shares need to be collected from other participants which hold them. At this time, a participant requested of a share does not always transfer the distributed value to the reconstructor without forgery. Note that “forgery” means not only intentional one but also an unintended modification such as breakdown of a device or a mere error.
Reconstructing a secret with a forged share may result in a value different from the secret. To prevent this, secret sharing schemes require a method capable of detecting at high probability the presence of a forged value in shares used for reconstruction. Depending on the operation form, shares are selected by various means. The forged value detection ratio needs to be high regardless of a probability distribution used to select shares. As techniques for solving these problems, there have been known methods in reference 2 (Martin Tompa, Heather Woll, “How to Share a Secret with Cheaters”, Journal of Cryptology, vol. 1, pages 133-138, 1988), reference 3 (Wakaha Ogata, Kaoru Kurosawa, Douglas R. Stinson, “Optimum Secret Sharing Scheme Secure Against Cheating”, SIAM Journal on Discrete Mathematics, Vol. 20, No. 1, pages 79-95, 2006), reference 5 (Satoshi Obana and Toshinori Araki, “Almost Optimum Secret Sharing Schemes Secure Against Cheating for Arbitrary Secret Distribution”, Advances in Cryptology—Asiacrypt 2006, Lecture Notes in Computer Science 4284, pp. 364-379, 2006), and reference 6 (Toshinori Araki, “Efficient (k,n) Threshold Secret Sharing Schemes Secure Against Cheating from n−1 Cheaters”, Proceedings of ACISP 2007, Lecture Notes in Computer Science 4586, pp. 133-142, 2007).
Reference 2 describes a (k,n) threshold scheme capable of detecting, at a probability of (1−ε), cheating of forging (k−1) shares at most by referring to (n−1) shares regardless of a probability distribution used to select a secret. According to a method described in reference 1 (Adi Shamir, “How to Share a Secret”, Comm. ACM, 22 (11), 612-613 (1979)), when a secret is regarded as a set of elements s, shares are a set of elements ((s−1)(k−1)/ε+k)^2.
Reference 3 describes a (k,n) threshold scheme capable of detecting, at a probability of (1−ε), cheating of forging (k−1) shares at most by referring to (k−1) shares on condition that a secret is selected in accordance with a uniform probability distribution. In the method described in reference 3, when a secret is regarded as a set of elements s, shares are a set of elements (1+(s−1)/8). An (n,n) threshold secret sharing scheme is described in reference 4 (J. Benaloh and J. Leichter, “Generalized Secret Sharing and Monotone Functions”, in Advances in Cryptology—CRYPTO '88, S. Goldwasser, Ed., Lecture Notes in Computer Science 403, pages 27-35, 1989).
Reference 5 describes a secret sharing scheme capable of detecting, at a probability of (1−ε), cheating of forging (k−1) shares at most by referring to (k−1) shares regardless of a probability distribution used to select a secret. In the method described in reference 5, when a secret is regarded as a set of elements s, shares are a set of elements s/(ε^2).
Reference 6 describes a (k,n) threshold scheme capable of detecting, at a probability of (1−ε), cheating of forging (k−1) shares at most by referring to (n−1) shares regardless of a probability distribution used to select shares. According to the method described in reference 1, when a secret is regarded as a set of elements s, and s≦1/ε holds, shares are a set of s^2/ε.